package medium;

public class T45 {
    public static void main(String[] args) {
        System.out.println(jump(new int[]{2, 3, 0, 1, 4}));
    }

    static int totalJump;
    static int[] numsC;
    public static int jump(int[] nums) {
        totalJump = 0;
        numsC = nums;
        dp(nums.length - 1);
        return totalJump;
    }

    /**
     * 贪心算法
     * dp[j]：能直接跳到j小标的最小下标
     * 2 3 1 1 4
     *
     * 先找能直接挑战到最后位置的最远下班，下标1的值为3，刚好能跳到最后一个；在以下标为1的位置为终点，找到能直接跳转到下标1位置的最远距离，即为下标0；
     * 所以最快跳到终点的跳法是0->1->4，只需要2步
     */
    public static void dp(int j) {
        if (j == 0) {
            return;
        }
        for (int i = 0; i < j; i++) {
            int jump = j - i;
            if (numsC[i] >= jump) {
                totalJump++;
                dp(i);
                break;
            }
        }
    }
}
